# 82/100 动态规划-杨辉三角
# leetcode第118题: https://leetcode.cn/problems/pascals-triangle/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/7
from leetcode import test


def generate(numRows: int) -> list[list[int]]:
    if numRows < 2:
        return [[1]]

    dp = [[0] * (i + 1) for i in range(numRows)]
    dp[0][0] = 1
    for i in range(1, numRows):
        for j in range(i + 1):
            if j == 0 or j == i:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

    return dp


if __name__ == '__main__':
    inp = [{"numRows": 5}, {"numRows": 1}, {"numRows": 2}]
    out = [[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]],
           [[1]],
           [[1], [1, 1]], ]

    test.test_function(generate, inp, out)
